package leetcode.Hot100;

/**
 * @author Cheng Jun
 * Description: 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 * <p>
 * 说明：每次只能向下或者向右移动一步。
 * https://leetcode-cn.com/problems/minimum-path-sum/
 * @version 1.0
 * @date 2021/11/26 10:04
 */
public class minPathSum {

    public static void main(String[] args) {
        int[][] ints = new int[][]{new int[]{1, 2, 3}, new int[]{4, 5, 6}};
        System.out.println(minPathSum(ints));
    }

    // 动态规划：grid[i][j] 路径的最小和 只和 Math.min(grid[i-1][j], grid[i][j-1])有关
    static int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        // 注意初始化 第一行 和第一列
        for (int j = 1; j < n; j++) {
            grid[0][j] += grid[0][j - 1];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] = grid[i][j] + Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[m - 1][n - 1];
    }
}
